The invention concerns generally the technology of using encoding, decoding and eventual retransmission for providing error-free communications over a noisy channel. Especially the invention concerns the selection and organisation of encoding and decoding in relation to the amount of data to be transmitted in the form of packets.
Error detection codes are generally used to provide the receiver of digital information with adequate means for detecting, whether a certain piece of received digital information contained errors. An example of an error detection code is the addition of a CRC (Cyclic Redundancy Check) checksum to each piece of data of certain size. Error correction coding is used to enhance the probability of correct reception of digital information even when a noisy transmission channel is suspected to introduce errors. An example of error correction coding is the use of a convolutional encoder at the transmitting end and a Viterbi decoder at the receiving end. A more advanced example of error correction coding is the use of a turbo encoder at the transmitting end and an iterative turbo decoder at the receiving end. A coding scheme in which both error detection coding and error correction coding are applied to the same transmitted data is generally known as hybrid coding.
FIG. 1 illustrates a known example of transmitting packet data in a frame 100. In digital telecommunication systems it is customary to arrange the transmission of data in frames of constant duration, e.g. 10 ms. The capacity of a frame in bits depends on the modulation method employed, but is easily very large, like several thousands of bits. In the transmission of packet data it would often be incovenient and inefficient to arrange the data to be transmitted into such large packets. Instead, a smaller packet size is used and several consecutive packets are transmitted within a single frame. In FIG. 1 we see four packets 101, 102, 103 and 104 within the frame 100. The packets are also known as Protocol Data Units or PDUs.
According to a known hybrid coding scheme the transmitting device will first encode the packets 101, 102, 103 and 104 with an error detection code and then with an error correction code. Each packet is encoded separately. Both parts of the hybrid coding scheme introduce some overhead bits to the packets: an error detection code requires typically the calculation of a checksum which is added to the information bits, and an error correction code introduces some tail bits for the error correction code to terminate at a desired state at the end of the packet. FIG. 1 illustrates the overhead bits introduced through encoding schematically as a hatched block at the end of each packet. The overhead bits need not always be at the end of each packet. A typical transmitter will additionally interleave the encoded bits of the consecutive packets over a certain interleaving length, which most advantageously coincides with the length of the frame.
A typical receiver will first receive the whole encoded and interleaved frame and de-interleave it so that each packet is again separately accessible. Thereafter the receiver will apply Viterbi decoding, iterative decoding or corresponding error correction decoding to each packet to remove the error correction code and to reconstruct the packet (which is still in the error detection coded form) as realiably as possible. Finally the receiver will remove the error detection code and check, whether the packet contained errors. Those packets where errors are detected are put aside. If and when the communication connection allows for messaging in the return direction, the receiver will convey to the transmitter an ARQ or Automatic Repeat reQuest concerning the error-infected packets.
A large number of different practices are known for arranging for corrective retransmissions. An inefficient but simple alternative is to restart the transmission from the first encountered error. A more advanced alternative is selective retransmission in which only those frames or packets are retransmitted in which errors were detected. In an even more advanced version the selective retransmission does not contain an identical copy of the whole packet of frame but only some additional bits that should help the receiver to correct the detected errors. The receiver has also a number of alternative ways to handle the received retransmissions: basically it may either use the retransmitted information to replace the original one or it may apply some kind of maximal ratio combining to exploit essentially all information received so far in the reconstruction of the original packet.
The problem of the arrangement of FIG. 1 is the relatively large amount of overhead information that must be introduced at the encoding stage. A very natural basic rule is that the amount of overhead is directly proportional to the probability of immediate successful decoding but inversely proportional to the effiency of use of the available communication resources (time, bandwidth). A more detailed analysis shows that for example a convolutional code with a constraint length K (i.e. memory length K-1) requires K-1 tail bits to be added to the end of each independently encoded unit of information. From the theory of CRC codes it is known that an upper bound for the probability of an undetected error is in the order of 2xe2x88x92b where b is the number of added CRC bits. The task of a system designer is to select the amount of overhead so that it strikes a desired balance between robustness and efficiency.
It is an object of the present invention to provide a method for transmitting packet data in frames with a good efficiency and acceptable robustness against errors. It is a further object of the invention to provide a transmitter and a receiver that take advantage of such a method.
The objects of the invention are achieved by using a hybrid coding scheme in which a common error detection code is applied to a first number of packets and an error correction code is separately applied to each group of a second number of packets, said second number being smaller than said first number.
The receiving method according to the invention requires that the information to be received
is arranged in discrete subunits so that a predetermined number of subunits correspond to a superunit and
is encoded with a certain error detection code, corresponding to a certain error detection decoding method, and additionally with a certain error correction code, corresponding to a certain error correction decoding method. The receiving method is characterised in that it comprises the steps of
error correction decoding a superunit,
during the error correction decoding, separately estimating the decoding reliability of each subunit of the superunit to be decoded,
error detection decoding the error correction decoded superunit,
during the error detection decoding, detecting whether or not there were errors in the superunit to be decoded, and
if there were detected errors in the decoded superunit, arranging for partial retransmissions of the decoded superunit on the basis of the estimated reliabilities of the subunits.
The invention applies also to a transmission method having the characteristic steps of
arranging the digital information to be transmitted into discrete subunits and composing a superunit from a predetermined number of subunits,
encoding said superunit continuously with a certain error detection code corresponding to a certain error detection decoding method,
encoding said superunit continuously with a certain error correction code, corresponding to a certain error correction decoding method,
transmitting the encoded superunit from the transmitting device to the receiving device,
error correction decoding said superunit,
during the error correction decoding, separately estimating the decoding reliability of each subunit of the superunit to be decoded,
error detection decoding the error correction decoded superunit,
during the error detection decoding, detecting whether or not there were errors in the superunit to be decoded, and
if there were detected errors in the decoded superunit, arranging for partial retransmissions of the decoded superunit on the basis of the estimated reliabilities of the subunits.
The invention applies further to a transmitting apparatus comprising
buffering means for conjoining a predefined number of subunits of information into a superunit,
error detection encoding means for error detection encoding the information to be transmitted,
error correction encoding means for error correction encoding the information to be transmitted and
retransmission means for providing retransmissions concerning selected portions of the information to be transmitted. The transmitting apparatus is characterised in that
the error detection encoding means and error correction encoding means are arranged to encode completely conjoined superunits,
the retransmission means are arranged to provide retransmissions concerning selected subunits and
the transmitting device further comprises multiplexing means for multiplexing encoded conjoined superunits and retransmissions concerning selected subunits into transmission frames.
Additionally the invention applies to a receiving apparatus which is characterised in that it comprises
error correction decoding means for error correction decoding a superunit and estimating the decoding reliability of each subunit contained within it,
error detection decoding means for error detection decoding a superunit and detecting whether or not there were errors in it and
retransmission control means for identifying, as a response to a nonzero number of errors detected in a decoded superunit, a predefined number of the subunits within the decoded superunit as suspicious on the basis of the estimated reliabilities of the subunits and for generating retransmission requests concerning the subunits identified as suspicious.
The invention relies on the fact that a decoder for decoding an error correction code is able to produce a so-called reliability metric which is an indication of the reliability of a certain performed decoding operation. In other words, after having decoded a certain piece of information the error correction code decoder may say that the decoding result represents the original piece of information with a certain probability. Some decoders may even give several alternative decoding results and their associated reliability metrics.
According to the invention, the reliability metric is utilised in the following way. For a relatively large amount of information there is a single error detection code. The same information is further encoded with an error correction code. Within said relatively large amount of information there are smaller subamounts of information. During the decoding process, a separate reliability metric is generated for each subamount of information. If the decoding of the error detection code indicates that the large amount of information contained an error or errors, the decoder expects that the error(s) appeared in those subamounts of information which had the lowest reliability metric. A retransmission will be requested for a selected number of those subamounts of information where the error(s) were likely to reside, or other corrective measures are taken to replace the erroneous data.
For selecting the xe2x80x9csuspiciousxe2x80x9d subamounts of information several alternatives are available. The receiver may arrange all subamounts of information into an order of descending values of the reliability metric, use the error detection code to estimate the number of occurred transmission errors and ask for a retransmission concerning an equal number of subamounts of information from the bottom of the list. Another alternative is that the receiver will use the distribution of the reliability metrics and/or the estimated number of occurred transmission errors (if available) to establish a threshold value for the reliability metric to be acceptable, and ask for a retransmission concerning all those subamounts of information that fall under the threshold. Different combinations of these alternative methods are also available.
If the error correction decoder is of the type that provides, for a single subamount of information, a list of mutually alternative decoded sequences in a descending order of estimated decoding reliability, the invention allows for several operational alternatives. A natural choice is to select the sequence at the top of the list to be the primary representative for each subamount of information, and its reliability metric as the primary reliability metric for that subamount of information. If the error detection decoding of the large amount of information has indicated the presence of errors, suspicious subamounts of information are selected by using the primary reliability metrics as described above. For at least one selected suspicious subamount of information a number of the candidate sequences from the list may be tried first before asking for retransmissions.
According to an advantageous embodiment of the invention, the relatively large amount of information corresponds to a frame or other suitable assemblage of packets and a subamount of information corresponds to a packet.